1. Field of the Invention
This invention relates generally to packet network devices, and more particularly to a method and apparatus for traffic management within such a device based on lookup cost.
2. Description of Related Art
Packet network devices receive and send data in finite-length packets. A packet generally encapsulates the data in a payload section, with one or more header sections providing instructions for delivery and interpretation of the payload. Multi-port packet network devices such as switches and routers use a variety of schemes to direct packets along a network path from a sender to a destination. Virtually all of these schemes involve reading at least one packet header from each packet, and interpreting the header information in order to forward each packet towards its destination. Depending on the types of headers used, one or more headers may also be modified before the packet is forwarded.
FIG. 1 shows a section of a prior art network device 100. The illustrated section of network device 100 processes packets received on four different ports A-D. Each port connects to a port FIFO (First-In First-Out buffer) capable of queuing packets while the packets await processing. Four port A packets A1, A2, A3, A4 are shown in port FIFO 110A, three port B packets B1, B2, B3 are shown in port FIFO 110B, three port C packets C1, C2, C3 are shown in port FIFO 110C, and three port D packets D1, D2, D3 are shown in port FIFO 110D.
An arbiter 120 selects packets from port FIFOs 110A-D according to an arbitration scheme that apportions access to the device among the ports. Arbiter 120 passes the selected packets to packet processing 130, where forwarding actions and packet modifications are performed.
Many switches are capable of operation in an “oversubscribed” bandwidth configuration. In FIG. 1, for example, device 100 may be designed with a merged FIFO 150 that can merge data from only three input ports at full line rate, and yet four ports are served. As long as each of the four ports receives with 75% average utilization or less, device 100 can process all traffic received. There may be some time periods, however, where near-line-rate traffic is received on all four ports at once. When this occurs, some sort of dropping mechanism is needed to manage traffic intelligently. Random early drop unit 140 provides such a service by sensing impending congestion in the device, and randomly dropping packets when congestion is imminent. Sophisticated devices have the capability to determine which of the input ports are exceeding an assigned bandwidth profile, and increase the probability that a packet from an out-of-profile port will be dropped should dropping be necessary.
In FIG. 1, processed packets are queued in merged FIFO 150 to await forwarding to their assigned output ports. FIFO 150 did not have sufficient buffer space for processed packets A0, B0, C0, and D0. Accordingly, random early drop unit 140 selected packet C0 and dropped that packet to keep the device within its capacity limits.